package demo9;


import java.util.*;
public class Solution {
    //    //2.剑指 Offer II 081. 允许重复选择元素的组合(回溯二刷)
//    private List<List<Integer>> list = new ArrayList<>();
//    private List<Integer> path = new ArrayList<>();
//
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        dfs(candidates, target, 0);
//        return list;
//    }
//
//    private void dfs(int[] candidates, int target, int begin) {
//        if (target == 0) {
//            list.add(new ArrayList<>(path));
//            return;
//        } else if (target < 0) {
//            return;
//        }
//        for (int i = begin; i < candidates.length; i++) {
//            path.add(candidates[i]);
//            dfs(candidates, target - candidates[i], i);
//            path.remove(path.size() - 1);
//        }
//
//    }
//
//    //3.剑指 Offer II 082. 含有重复元素集合的组合(剪枝优化)
//    private Set<List<Integer>> list = new HashSet<>();
//    private List<Integer> path = new ArrayList<>();
//
//    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        boolean[] flag = new boolean[candidates.length];
//        Arrays.sort(candidates);
//        dfs(candidates, target, flag, 0);
//        return new ArrayList<>(list);
//    }
//
//    private void dfs(int[] candidates, int target, boolean[] flag, int begin) {
//        if (target == 0) {
//            list.add(new ArrayList<>(path));
//            return;
//        } else if (target < 0) {
//            return;
//        }
//        for (int i = begin; i < candidates.length; i++) {
//            if(flag[i]) {
//                continue;
//            }
//            if(i > begin && candidates[i] == candidates[i - 1]) {//剪枝防止重复计算
//                continue;
//            }
//            flag[i] = true;
//            path.add(candidates[i]);
//            dfs(candidates, target - candidates[i], flag, i + 1);
//            flag[i] = false;
//            path.remove(path.size() - 1);
//        }
//    }
//
//    //4.剑指 Offer II 083. 没有重复元素集合的全排列(回溯二刷)
//    private List<List<Integer>> list = new ArrayList<>();
//    private List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> permute(int[] nums) {
//        boolean[] flag = new boolean[nums.length];
//        dfs(nums, flag);
//        return list;
//    }
//
//    private void dfs(int[] nums, boolean[] flag) {
//        if(path.size() == nums.length) {
//            list.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = 0; i < nums.length; i++) {
//            if(flag[i]) {
//                continue;
//            }
//            flag[i] = true;
//            path.add(nums[i]);
//            dfs(nums, flag);
//            flag[i] = false;
//            path.remove(path.size() - 1);
//        }
//    }
//
//    //5.剑指 Offer II 084. 含有重复元素集合的全排列 (回溯二刷 set去重)
//    private Set<List<Integer>> list = new HashSet<>();
//    private List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        boolean[] flag = new boolean[nums.length];
//        Arrays.sort(nums);
//        dfs(nums, flag);
//        return new ArrayList<>(list);
//    }
//
//    private void dfs(int[] nums, boolean[] flag) {
//        if(nums.length == path.size()) {
//            list.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = 0; i < nums.length; i++) {
//            if(flag[i]) {
//                continue;
//            }
//            flag[i] = true;
//            path.add(nums[i]);
//            dfs(nums, flag);
//            flag[i] = false;
//            path.remove(path.size() - 1);
//        }
//    }
//    //回溯剪枝
//    private List<List<Integer>> list = new ArrayList<>();
//    private List<Integer> path = new ArrayList<>();
//    public List<List<Integer>> permuteUnique(int[] nums) {
//        boolean[] flag = new boolean[nums.length];
//        Arrays.sort(nums);
//        dfs(nums, flag);
//        return list;
//    }
//
//    private void dfs(int[] nums, boolean[] flag) {
//        if(nums.length == path.size()) {
//            list.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = 0; i < nums.length; i++) {
//            if(flag[i]) {
//                continue;
//            }
//            if(i > 0 && nums[i] == nums[i - 1] && !flag[i - 1]) {
//                continue;
//            }
//            flag[i] = true;
//            path.add(nums[i]);
//            dfs(nums, flag);
//            flag[i] = false;
//            path.remove(path.size() - 1);

//    }
//
//    //6.剑指 Offer II 085. 生成匹配的括号(回溯二刷)
//    private List<String> list = new ArrayList<>();
//    private StringBuilder path = new StringBuilder();
//    private int ans;
//    public List<String> generateParenthesis(int n) {
//        char[] chs = {'(', ')'};
//        dfs(n, chs);
//        return list;
//    }
//
//    private void dfs(int n, char[] chs) {
//        if(path.length() == n * 2 && ans == 0) {
//            list.add(new String(path));
//            return;
//        } else if(path.length() == n * 2 && ans != 0) {
//            return;
//        }
//        for(int i = 0; i < 2; i++) {
//            if(ans < 0 || ans > n) {
//                return;
//            }
//            if(i == 0) {
//                ans++;
//            } else {
//                ans--;
//            }
//            path.append(chs[i]);
//            dfs(n, chs);
//            if(i == 0) {
//                ans--;
//            } else {
//                ans++;
//            }
//            path.deleteCharAt(path.length() - 1);
//        }
//    }
//
//    //7.复原 IP 地址(回溯剪枝)
//    private List<String> list = new ArrayList<>();
//    private List<String> path = new ArrayList<>();
//    public List<String> restoreIpAddresses(String s) {
//        dfs(s, 0);
//        return list;
//    }
//
//    private void dfs(String s, int begin) {
//        if(path.size() > 4) {
//            return;
//        }
//        if(path.size() == 4 && begin == s.length()) {
//            StringBuilder tmp = new StringBuilder();
//            for(int i = 0; i < 4; i++) {
//                tmp.append(path.get(i));
//                if(i < 3) {
//                    tmp.append(".");
//                }
//            }
//            list.add(tmp.toString());
//        }
//        for(int i = begin; i < s.length(); i++) {
//            String str = s.substring(begin, i + 1);
//            if(!isValue(str)) {
//                continue;
//            }
//            path.add(str);
//            dfs(s, i + 1);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    private boolean isValue(String str) {
//        if(str.length() == 1) {
//            return true;
//        }
//        if(str.length() > 3) {//防止parseInt溢出
//            return false;
//        }
//        if(Integer.parseInt(str) > 255) {
//            return false;
//        }
//        if(str.charAt(0) == '0') {
//            return false;
//        }
//        return true;
//    }
//
//    //8.剑指 Offer II 087. 复原 IP (回溯二刷+剪枝优化)
//    private List<String> list = new ArrayList<>();
//    private List<String> path = new ArrayList<>();
//    public List<String> restoreIpAddresses(String s) {
//        dfs(s, 0);
//        return list;
//    }
//
//    private void dfs(String s, int begin) {
//        if(path.size() == 4 && begin == s.length()) {
//            StringBuilder str = new StringBuilder();
//            for(int i = 0; i < 4; i++) {
//                str.append(path.get(i));
//                if(i < 3) {
//                    str.append(".");
//                }
//            }
//            list.add(str.toString());
//            return;
//        } else if(path.size() == 4 && begin != s.length()) {
//            return;
//        }
//        for(int i = begin; i < s.length(); i++) {
//            String str = s.substring(begin, i + 1);
//            if(!isValue(str)) {
//                continue;
//            }
//            path.add(str);
//            dfs(s, i + 1);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    private boolean isValue(String str) {
//        if(str.length() == 1) {
//            return true;
//        }
//        if(str.length() > 3) {
//            return false;
//        }
//        if(Integer.parseInt(str) > 255) {
//            return false;
//        }
//        if(str.charAt(0) == '0') {
//            return false;
//        }
//        return true;
//    }

//
//    //9.剑指 Offer II 102. 加减的目标值(回溯)
//    private int count;
//    public int findTargetSumWays(int[] nums, int target) {
//        dfs(nums, target, 0);
//        return count;
//    }
//
//    private void dfs(int[] nums, int target, int index) {
//        if(target == 0 && index == nums.length) {
//            count++;
//            return;
//        } else if(index == nums.length) {
//            return;
//        }
//        for(int i = 0; i < 2; i++) {
//            int ans = 1;
//            if(i != 0) {
//                ans = -1;
//            }
//            dfs(nums, target - nums[index] * ans, index + 1);
//        }
//    }

    //剑指 Offer II 110. 所有路径(双回溯)
    private List<List<Integer>> list = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int len = graph.length;
        path.add(0);
        dfs(graph, len - 1);
        return list;
    }

    private void dfs(int[][] graph, int key) {
        if(key == path.get(path.size() - 1)) {
            list.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0; i < graph.length; i++) {
            if(path.get(path.size() - 1) != i) {
                continue;
            }
            for(int j = 0; j < graph[i].length; j++) {
                path.add(graph[i][j]);
                dfs(graph, key);
                path.remove(path.size() - 1);
            }
        }
    }
}

class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] arr = {{4, 3, 1}, {3, 2, 4}, {3}, {4},{}};
        solution.allPathsSourceTarget(arr);
    }
}